# coding: utf-8
# Two Sum: https://leetcode-cn.com/problems/two-sum/

#使用哈希表dict
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #哈希表
        table=dict()

        l=len(nums)
        for i in range(0,l):
            val=target-nums[i]
            if table.has_key(val):
                return [table.get(val),i]
            else:
                table[nums[i]]=i
        return []

#使用二分查找+保留排序后的下标
class Solution2(object):
    #exIdx是要排除的下标
    def binarySearch(self, nums, item, exIdx):
        low=0
        high=len(nums)-1
        while low<=high:
            mid=(low+high)/2
            guess=nums[mid]
            if item==guess and mid!=exIdx:
                return mid
            elif item<guess:
                high=mid-1
            else:
                low=mid+1
        return None
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        #保留排序后的下标
        sortedArr=sorted(enumerate(nums), key=lambda x: x[1])
        print(sortedArr)
        indexArr=[x[0] for x in sortedArr]
        valArr=[x[1] for x in sortedArr]
        l=len(valArr)

        for i in range(0,l):
            pos=self.binarySearch(valArr,target-valArr[i],i)
            if pos!=None:
                return sorted([indexArr[i],indexArr[pos]])
        return []

sol=Solution2()
res=sol.twoSum([5,75,25],100)
print(res)